#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 2e6 + 10, MOD = 100003;

int dist[N]; 
bool st[N];
int f[N];

vector<int> edges[N];

int n, m;

void bfs()
{
	memset(dist, 0x3f, sizeof dist);
	queue<int> q;
	q.push(1);
	dist[1] = 0;
	f[1] = 1;
	while(q.size())
	{
		auto t = q.front(); q.pop();
		for(auto x : edges[t])
		{
			if(dist[t] + 1 < dist[x])
			{
				dist[x] = dist[t] + 1;
				f[x] = f[t];
				q.push(x);	
			} 
			else if(dist[t] + 1 == dist[x])
			{
				f[x] += f[t];
				f[x] %= MOD;
			}
		}
	}
} 

void dijkstra()
{
	memset(dist, 0x3f, sizeof dist);
	priority_queue<PII, vector<PII>, greater<PII>> heap;
	heap.push({0, 1}); 
	dist[1] = 0;
	f[1] = 1;
	while(heap.size())
	{
		auto p = heap.top(); heap.pop();
		int t = p.second;
		if(st[t]) continue;
		st[t] = true;
		for(auto x : edges[t])
		{
			if(dist[t] + 1 < dist[x])
			{
				dist[x] = dist[t] + 1;
				f[x] = f[t];
				heap.push({dist[x], x});
			}
			else if(dist[t] + 1 == dist[x])
			{
				f[x] += f[t];
				f[x] %= MOD;
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int a, b; 
		scanf("%d%d", &a, &b);
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
//	bfs();
	dijkstra();
	for(int i = 1; i <= n; i++) cout << f[i] << endl;
	return 0;
}

